package com.example.algorithm.dynamicprogramming;

/**
 * 我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）
 *  现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
 *  返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
 *
 *  示例 1：
 *  输入：D = ["1","3","5","7"], N = 100
 * 输出：20
 * 解释：
 * 可写出的 20 个数字是：
 * 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
 *
 *  示例 2：
 *  输入：D = ["1","4","9"], N = 1000000000
 * 输出：29523
 * 解释：
 * 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，81 个四位数字，243 个五位数字，729 个六位数字，2187 个七位数字，6561 个八位数字
 *  和 19683 个九位数字。
 * 总共，可以使用D中的数字写出 29523 个整数。
 *
 */
public class Leetcode902_AtMostNGivenDigitSet {
    public static void main(String[] args) {
        String[] digits = {"1","3","5","7"};
        int n = 100;

        System.out.println(new Solution().atMostNGivenDigitSet(digits, n));
    }

    static class Solution {

        public int atMostNGivenDigitSet1(String[] digits, int n) {
            String str = String.valueOf(n);
            int k = str.length(); // 统计 n 有多少位数
            int res1 = 0;
            // 首先计算满足条件的所有小于 k 位数字的有多少个数
            for (int i = 1; i < k; i++) {
                res1 += Math.pow(digits.length, i);
            }

            // 然后计算满足条件的有 k 位数字的数的个数(动态规划)
            int[] dp = new int[k + 1]; // dp[i] 表示小于等于 n 中最后 |n| - i 位数的合法数的个数
            dp[k] = 1;
            for (int i = k - 1; i >= 0; --i) {
                int tmp = str.charAt(i) - '0';
                for (String d: digits) {
                    if (Integer.valueOf(d) < tmp)
                        dp[i] += Math.pow(digits.length, k - i - 1);
                    else if (Integer.valueOf(d) == tmp)
                        dp[i] += dp[i + 1];
                }
            }

            return res1 + dp[0];
        }

        public int atMostNGivenDigitSet(String[] digits, int n) {
            return atMostNGivenDigitSet1(digits, n);
        }
    }
}
